package sort;

/**
 * @author zxl
 * @version 1.0
 * @date 2021/12/5 11:28
 * 二分查找   前提是有序   不稳定   优化插入排序
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] a = new int[]{1,2,3,5,11,12,21,31,32,43,45,53,54,56,67,76,76,87,90};
        int num = getNum(a, 25);
        System.out.println(num);
    }

    /**
     * 二分查找
     * @param array
     * @param num
     * @return  返回索引
     */
    public static int getNum(int[] array,int num){
        //头部
        int startNum = 0;
        //尾部
        int endNum = array.length;
        //当头部小于尾部时
        while (startNum < endNum){
            // 位运算  相当于 (startNum + endNum)/2
            int mid = (startNum + endNum) >> 1;
            // 当查找的数在中间的前面
            if(num < array[mid]){
                // 尾部变为中间
                endNum = mid;
            // 当查找的数在中间的后面
            }else if(num > array[mid]){
                // 开始位置变为 中间+1
                startNum = mid + 1;
            }else {
                // 当等于中间  返回结果
                return mid;
            }
        }
        // 当为查询到结果返回-1
        return -1;
    }
}
